package com.ShangGuiGu.Tree;

import lombok.Data;
import lombok.Getter;
import lombok.Setter;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 赫夫曼树
 *
 * @author Lenovo
 * <p>
 * 给定n个权值作为n个叶子结点，构造一棵二叉树
 * 若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树
 * 也称为赫夫曼树，别名哈夫曼树
 * <p>
 * 权值是你当前节点的所赋的值就是当前节点的权
 * 路径是你根节点到当前节点的   节点数-1
 * <p>
 * <p>
 * 如何用一个数组来创建哈夫曼树
 * 先对数组进行从小到大的排序
 * 然后取出节点权值最小的两颗二叉树组成一个新的二叉树，这两课二叉树的根节点是两个节点权值的和
 * 然后再重复以上操作，直至所有的数字都被处理，形成了哈夫曼树
 */
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int arr[] = {13, 7, 8, 3, 29, 6, 1};

        Tree huffmanTree = createHuffmanTree(arr);
        preOrder(huffmanTree);

    }

    /**
     * 创造哈夫曼树的方法
     *
     * @param arr
     */
    public static Tree createHuffmanTree(int[] arr) {
        //将数组的数据遍历加入到集合中
        List<Tree> trees = new ArrayList<Tree>();
        for (int i : arr) {
            trees.add(new Tree(i));
        }

        while (trees.size() > 1) {
            //排序
            Collections.sort(trees);

            //将集合中最小的两个tree的值相加形成一个新的tree
            Tree left = trees.get(0);
            Tree right = trees.get(1);
            //组成一个新二叉树并且加入集合中
            Tree root = new Tree(left.getData() + right.getData());
            //重新定向
            root.setLeft(left);
            root.setRight(right);
            //并且删除这两个tree
            trees.remove(left);
            trees.remove(right);

            trees.add(root);
        }

        return trees.get(0);

    }

    public static void preOrder(Tree tree){
        if (tree !=null){
            tree.preOrder();
        }else {
            System.out.println("树为空");
        }
    }


}

/**
 * 构建一颗二叉树用来存储数据
 *
 * @author Lenovo
 * 最后将他变成哈夫曼树
 */
@Data
@Setter
@Getter
class Tree implements Comparable<Tree> {
    private int data;
    private Tree left;
    private Tree right;

    public Tree(int data) {
        this.data = data;
    }

    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }

    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data=" + data +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    @Override
    public int compareTo(Tree o) {
        return this.data - o.data;
    }
}
